package dp.practice2.knapsack_01_maxvalue;

import java.util.Arrays;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        int m = 10;
        int[] A = new int[]{1, 4, 2, 3, 6};
        int[] V = new int[]{3, 4, 1, 2, 7};
        System.out.println(knapsack(m, A, V));
    }

    public static int knapsack(int m, int[] A, int[] V) {
        if (m == 0 || A == null || V == null || A.length == 0) {
            return 0;
        }
        int len = A.length;
        int[][] count = new int[len][m + 1];
        for (int i = 0; i < m + 1; i++) {
            if (i >= A[0]) {
                count[0][i] = V[0];
            }
        }
        for (int i = 1; i < len; i++) {
            for (int j = 1; j < m + 1; j++) {
                if (j >= A[i]) {
                    count[i][j] = Math.max(count[i - 1][j], count[i - 1][j - A[i]] + V[i]);
                } else {
                    count[i][j] = count[i - 1][j];
                }
            }
        }
        List<int[]> list = Arrays.asList(count);
        list.forEach(e -> {
            System.out.println(Arrays.toString(e));
        });
        return count[len - 1][m];
    }
}
